package com.levi.stack;

/**
 * @author shentong
 * @date 2021/8/26 21:21
 * @Description 栈实现计算器(不带括号)
 * 实现思路:
 * 1.扫描表达式，判断是数字还是运算符，分别放到数栈和操作栈中
 * 2.如果是操作符
 *      2.1判断操作栈是不是空，如果是空则直接放进去
 *      2.2如果不是空，判断该操作符跟栈顶的操作符的优先级，如果优先级小于或者等于栈顶的操作符优先级，则把数栈弹出2个数据，操作栈弹出1一个操作符进行运算
 *      运算后的结果放进数栈，再把该操作符放进操作栈
 * 3.如果是数字，直接放进数栈中
 * 4.当循环遍历完毕之后，遍历数栈和操作栈，进行运算，遍历完毕后，数栈中只会剩下一个数据，这个数据就是计算结果(循环退出条件是操作栈为空)
 *
 * 注意:要判断数字是不是多位数，判断方法:如果这个字符是数字，判断左边的字符是不是数字，如果是数字，就把这个数字给弹出来，*10之后加这个数字再入栈
 *
 */
public class CalculatorByStack {
    public static void main(String[] args) {
        String expression = "301+209*6-2"; //结果是13
        CalculatorByStack.calcute(expression);
    }

    public static void calcute(String expression) {
        ArrayStack1 numStack = new ArrayStack1(10);
        ArrayStack1 operStack = new ArrayStack1(10);
        int index = 0;//用于遍历字符串
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char c = ' ';
        char d = ' ';
        while (index < expression.length()) {
            c = expression.charAt(index);

            //判断是不是操作符
            if (operStack.isOper(c)) {
                //判断操作符栈是不是空,是空的话直接放进去
                if (!operStack.isEmpty()) {
                    //如果不为空，比较运算符的优先级，如果操作符的优先级比操作栈栈顶的优先级小，就取数据进行运算
                    if (operStack.level(c) <= operStack.level(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.calculate(num1, num2, oper);
                        //运算结果放进数栈，再把该操作符放进操作栈
                        numStack.push(res);
                        operStack.push(c);
                    }else {
                        operStack.push(c);
                    }
                }else {
                    operStack.push(c);
                }
            }else {
                //因为得到的c是char类型，ascall码中字符和数字相差48,所以要减去48，才是数字的编码
                //判断是不是多位数
                if (index > 0) {
                    d = expression.charAt(index - 1);
                }
                if (!operStack.isOper(d) && d != 32){
                    int peek = numStack.peek();
                    numStack.pop();
                    numStack.push(peek*10+(c-48));
                }else numStack.push(c - 48);

            }
            index++;
        }
        //当遍历扫描完毕之后，就开始弹出数据并计算
        //如果操作符栈不为空，就一直计算
        while (!operStack.isEmpty()) {
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.calculate(num1, num2, oper);
            numStack.push(res);
        }
        //退出循环的时候数栈中只有一个数据，就是最后的结果
        System.out.printf("表达式%s的计算结果是:%d\n",expression,numStack.pop());
    }

}

class ArrayStack1{
    private int maxSize;//栈的最大值
    private int[] stack;//数组，用来放栈中的数据
    private int top = -1;//栈顶的位置 //初始值为-1

    public ArrayStack1(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
    }

    /**
     * 判断栈是否满
     * @return
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 入栈
     * @param value
     */
    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("栈已满,不能添加数据");
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈
     * @return
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 遍历栈中的数据，从栈顶开始遍历
     */
    public void list() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        for (int i = top; i >=0; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    /**
     * 判断符号的优先级
     * @param val
     * @return
     */
    public int level(int val) {
        if (val == '*' || val == '/') {
            return 1;
        }else if (val == '+' || val == '-'){
            return 0;
        } else return 0;
    }

    /**
     * 判断是不是操作符
     * @param val
     * @return
     */
    public boolean isOper(int val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    /**
     * 获取栈顶的数据
     * @return
     */
    public int peek() {
        return stack[top];
    }
    /**
     * 计算方法
     * @param num1
     * @param num2
     * @param oper
     * @return
     */
    public int calculate(int num1,int num2,int oper) {
        int result = 0;
        switch (oper){
            case '+':
                result =  num1 + num2;
                break;
            case '-':
                result =  num2 - num1;
                break;
            case '*':
                result =  num1 * num2;
                break;
            case '/':
                result =  num2 / num1;
                break;
            default:
                break;
        }
        return result;
    }


}